package _2022.hot100._4_寻找两个正序数组的中位数;

import java.util.Arrays;

/**
 * @author： YHSimon
 * @date： 2022-03-25 15:49
 */
public class Solution {
    //合并+排序
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int len=nums1.length+nums2.length;
        int target = len%2==0?(len/2-1):(len / 2);
        int[] num=new int[len];
        int count=0;
        for (int i = 0; i < nums1.length; i++,count++) {
            num[count]=nums1[i];
        }
        for (int i = 0; i < nums2.length; i++,count++) {
            num[count]=nums2[i];
        }
        Arrays.sort(num);
        return len%2==0?(num[target]+num[target+1])/2.0:num[target];
    }


    //直接遍历
    public double findMedianSortedArrays(int[] nums1,int[] nums2){
        int m=nums1.length;
        int n=nums2.length;
        int len=m+n;
        //left保存right的值
        int left=-1,right=-1;
        int aStart=0,bStart=0;
        for (int i = 0; i <=len/2 ; i++) {
            left=right;
            if(aStart<m&&(bStart>=n||nums1[aStart]<nums2[bStart])){
                right=nums1[aStart++];
            }else{
                right=nums2[bStart++];
            }
        }
        return len%2==0?(left+right)/2.0:right;
    }


//    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
////        double res=nums1.length==0?nums2[0]:nums1[0];
//        int len = nums1.length + nums2.length;
//        int target = len%2==0?(len/2-1):(len / 2);
//        int i1 = 0, i2 = 0;
//        int count=-1;
//        while (i1< nums1.length||i2<nums2.length) {
//            if (nums1[i1] <= nums2[i2]) {
//                count++;
//                if (count == target) {
//                    if (len % 2 == 0) {
//                        if (i1 + 1 < nums1.length && nums1[i1+1] <= nums2[i2]) {
//                            return (nums1[i1] + nums1[i1 + 1]) / 2.0;
//                        } else {
//                            return (nums1[i1] + nums2[i2]) / 2.0;
//                        }
//                    } else {
//                        return nums1[i1];
//                    }
//                } else {
//                    i1++;
//                }
//            } else {
//                count++;
//                if (count == target) {
//                    if (len % 2 == 0) {
//                        if (i2 + 1 < nums2.length && nums2[i2 + 1] <= nums1[i1]) {
//                            return (nums2[i2] + nums2[i2 + 1]) / 2.0;
//                        } else {
//                            return (nums1[i1] + nums2[i2]) / 2.0;
//                        }
//                    } else {
//                        return nums2[i2];
//                    }
//                } else {
//                    i2++;
//                }
//            }
//        }
//        if(len%2==0){
//            return nums1.length==0?(nums2[target]+nums2[target+1])/2.0:(nums1[target]+nums1[target+1])/2.0;
//        }else{
//            return nums1.length==0?nums2[target]:nums1[target];
//        }
//    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMedianSortedArrays2(new int[]{2,2,2}, new int[]{2,2,2,2}));
    }
}
